1. Field of the Invention
The present invention relates to the field of graphical editing tools, and in particular, to a method and system for interactive editing of geometric models based on level set operators.
2. Background Art
The creation of complex models for such applications as movie special effects, graphic arts, and computer-aided design can be a time-consuming, tedious, and error-prone process. One particular problem is how to effectively and properly store a 3D object into a digital representation for user manipulation. One of the solutions to the model creation problem is called 3D photography, wherein a 3D object is scanned directly into a digital representation. However, the scanned model is rarely in a final desired form. The scanning process is imperfect and introduces errors and artifacts, or the object itself may be flawed.
3D scans can be converted to polygonal and parametric surface meshes. Many algorithms and systems for editing these polygonal and parametric surfaces have been developed, but surface mesh editing has its limitations and must address several difficult issues. For example, it is difficult to guarantee that a mesh model will not self-intersect when performing a local editing operation based on the movement of vertices or control points, producing nonphysical, invalid results. If self-intersection occurs, it must be fixed as a post-process, which is a tedious task. The self-intersection problem is more acute in cases where the models are changing. Also, when merging two mesh models the process of clipping individual polygons and patches may produce errors when the elements are small and/or thin, or if the elements are almost parallel. In addition while it is not impossible to change the genus of a surface mesh model, it is certainly difficult and requires significant effort to maintain the consistency/validity of the underlying vertex/edge connectivity structure.
There exist several areas of research related to surface editing work. They are volumetric sculpting, mesh-based surface editing/fairing and implicit modeling. Volumetric sculpting provides methods for directly manipulating the voxels of a volumetric model. Constructive Solid Geometry (CSG) Boolean operations are commonly found in volume sculpting systems, providing a straightforward way to create complex solid objects by combining simpler primitives.
Performing CSG operations on mesh models is a long-standing area of research. Recently CSG operations were developed for multi-resolution subdivision surfaces, but this work did not address the problem of blending or smoothing the sharp features often produced by the operations. However, the smoothing of meshes has been studied on several occasions. A method has been developed for fairing irregular meshes using diffusion and curvature flow, demonstrating that mean-curvature based flow produces the best results for smoothing.
Besides explicit models such as polygonal models, there also exists a large body of surface editing work based on implicit models. This approach uses implicit surface representations of analytic primitives or skeletal offsets. One existing method describes an implicit modeling with techniques for performing blending, warping and boolean operations on skeletal implicit surfaces. Another address the converse problem of preventing unwanted blending between implicit primitives, as well as maintaining a constant volume during deformation.
What is desired is a new method of representing and editing 3D objects that allow efficient editing processes and overcome the problem of self-intersection. Furthermore, the method would have editing operators that are based on the mathematics of deforming implicit surfaces and not dependent on surfaces having underlying volumetric representations.